1. Field of the Invention
This invention relates to the creation of a minimized binary equation that differentiates true from false given a true truth table T and its complement F.
2. Description of the Related Art
A true truth table T 10 and its complement F 12 of the type shown in FIGS. 1a and 1b can be represented as binary equations 14 and 16 of the type shown in FIGS. 2a and 2b. T and F together comprise a set of binary input values for which a single binary digit of output is desired. The input combinations appearing in T must yield an output value of “true”; the input combinations appearing in F must yield an output value “false”. Any input combinations not explicitly appearing in either table may yield arbitrary output. The binary equation represents an efficient method of computing the output bit based on any given input string. Many techniques have been developed to pare down the binary equation to adequately represent a minimal mapping of the underlying system. This class of problem is referred to as “binary minimization”. Binary minimization is used in many applications such as digital logic circuit design, image processing and asynchronous design.
In digital circuit design, the truth tables represent the mapping from the logical inputs to a single bit output. The construction of logic gates to test explicitly for every possible input condition and give the appropriate output according to the map is tractable, but this approach is often suboptimal. In many applications, the resulting digital logic circuit would be too large, too slow and too expensive. Binary minimization is used to pare down the tests of the input condition necessary to adequately represent a minimal mapping to the output conditions and thus a minimum number of logic gates. Typical techniques include Karnaugh mapping and the Quine-McCluskey algorithm.
The general problem has been shown to be Nondeterminiic Polynomial (NP) time complete, thus any rigorous solution using currently known techniques will have solution times increasing exponentially with the size of the truth table. This status applies to the most frequently used formulation of the problem which uses simple OR logic to tie together multiple terms of intersecting (AND) input quantities, as well as variants using XOR logic, and a special variant.
Surface based combinatorial geometry (SBCG) represents a special variant of the general problem. The SBCG format consists of unbounded analytic surfaces knitted together by zone definitions using simple intersection logic and is commonly used in nuclear radiation transport, optical design, thermal radiation transport, visual scene rendering or other general ray-tracing applications. The SBCG format assumes that each segment of space is represented once and only once in the geometrical model. Conversely, the OR logic used in typical binary minimization approaches assumes that the various terms of the minimized equation can multiply represent truth, hence overlapping spatial regions are permitted in this context. For example (1 OR 1 OR 1 OR 0) in a geometry variant represents spatial overlap which is not allowed. Only one term may be true given any specific input condition to avoid spatial overlap. Thus, the existing body of algorithms cannot be directly applied to the combinatorial geometry problem because of its atypical implementation of OR logic. Other implementations of binary minimization have been deliberately constructed to use XOR logic in place of ORs, but even this substitution will permit forbidden overlaps to arise under the combinatorial geometry framework. However, any solution of the combinatorial geometry variant of the problem will satisfy the constraints of XOR logic; it won't take advantage of potential global features of that logic.
For example, the OR logic minimization of the truth table for [a′bc+ab′c+abc′+abc]=[ab+bc+ac]. However, this solution multiply specifies the region [abc], in fact, that quantity is permitted in each of the three terms of the solution. In the combinatorial geometry interpretation of this problem, one region of space would simultaneously exist in each of three distinct combinatorial zones. This sort of spatial overlap is not permitted in the radiation codes by definition. Use of XOR logic in this context can be seen to lose coherence to the zoning of space altogether, since XOR forces the definition of each sub-region to depend collectively on the definitions of all of them (one might ask to which term in [ab⊕bc⊕ac] abc belongs). The solution of the original problem under the combinatorial geometry variant, [ab+a′bc+ab′c], not only meets the needs of that logic set; it satisfies the requirements for a Boolean XOR solution as well.
There remains a need for an expedient calculation of a sufficient but not necessarily optimum solution for the general binary minimization problem. Furthermore, there remains a need for a solution to the combinatorial geometry variant of the binary minimization problem.